package oj;
//合并两个有序链表：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
public class Solution_21 {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode head1 = list1;
        ListNode head2 = list2;
        //工具结点：保存新的排序好的链表
        ListNode ansHead = new ListNode();
        ListNode ansLast = ansHead;
        //循环两个链表进行比较
        while (head1 != null && head2 != null){
            if(head1.val <= head2.val){
                ListNode cur = head1;
                head1 = head1.next;
                //将cur尾插到ansHead后边
                ansLast.next = cur;
                ansLast = cur;
            }else{
                ListNode cur = head2;
                head2 = head2.next;
                //尾插到结果链表中
                ansLast.next = cur;
                ansLast = cur;
            }
        }
        if(head1 != null){
            ansLast.next = head1;
        }else{
            ansLast.next = head2;
        }
        return ansHead.next;//ansHead是工具结点，该结点不保存任何有用信息，所以直接返回它的下一个结点即可
    }

    public static void main(String[] args) {
        ListNode n1 = new ListNode(100);
        ListNode n2 = new ListNode(200);
        ListNode n3 = new ListNode(300);
        n1.next = n2;
        n2.next = n3;
        ListNode list1 = null;
        ListNode list2 = null;
        Solution_21 solution_21 = new Solution_21();
        ListNode ans = solution_21.mergeTwoLists(list1,list2);
    }
}
